#include <stdio.h>
/*
void quick_sort(int a[],int N)
{
    1.选取主元 p
    2.把s={a[]\p}划分成两个子集
        2.1.a1={a∈s|a<=p}
        2.2.a2={a∈s|a>=p}
    3.a[]=quick_sort(a,n1)∪p∪quick_sort(a,n2)
}
*/
/***********交换函数***********/
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
/*************选取主元**************/
int pivot(int a[], int left, int right)
{
    int center = (left + right) / 2;
    if (a[left] > a[center])
    {
        swap(a[left], a[center]);
    }
    if (a[left] > a[right])
    {
        swap(a[left], a[right]);
    }
    if (a[center] > a[right])
    {
        swap(a[center], a[right]);
    }
    swap(a[center], a[right - 1]);
    return a[right - 1];
}
// 高性能
void quick_sort(int a[], int left, int right)
{
    if (left >= right)
        return;
    int p = pivot(a, left, right); //选主元采用中位数然后把中位数放在right-1的位置
    printf("%d:  ", p);
    int i = left;
    int j = right - 2;
    while (1)
    {
        while (a[i] < p)
        {
            i++;
        }
        while (a[j] > p)
        {
            j--;
        }
        if (i < j)
        {
            swap(a[i], a[j]);
        }
        else
        {
            break;
        }
    }
    //划分子集完毕
    // 把主元放在中间位置
    swap(a[i], a[right - 1]);
    //注意是谁和谁交换 因为主元一直都是在right-1的位置位于右侧
    //而最后结束的元素a[i]是大于主元的,所以应该是a[right-1]与a[i]进行交换
    // 主元 左侧
    quick_sort(a, left, i - 1);
    // 主元 右侧
    quick_sort(a, i + 1, right);
}

void q_s(int a[], int n)
{
    quick_sort(a, 0, n - 1);
}

//普通的快速排序  简单 考试专用
void common_qs(int a[], int left, int right)
{
    if (left >= right)
        return;
    int i = left + 1;
    int j = right;
    int p = a[left]; //选取最左侧的元素当做主元
    while (1)
    {
        while (a[i] < p)
        {
            i++;
        }
        while (a[j] > p)
        {
            j--;
        }
        if (i < j)
            swap(a[i], a[j]);
        else
            break;
    }
    //主元一直是处于数组最左侧的
    //a[j]最后是小于主元的
    swap(a[left], a[j]);
    common_qs(a, left, j - 1);
    common_qs(a, j + 1, right);
}
void c_q_s(int a[], int n)
{
    common_qs(a, 0, n - 1);
}

void stack_q_sort(int a[], int n)
{
    //初始化栈
    int stack[50];
    int top = -1;
    //左右下标进栈
    stack[++top] = 0;
    stack[++top] = n - 1;
    /* 左右下标入队
        inqueue(q,0);
        inqueue(q,n-1);
    */
    while (top >= 0)
    {
        int r = stack[top--];
        int l = stack[top--];
        /*入队
            int r = gethead(q);
            int l = gethead(q);
        */
        /*******quick_sort函数主体部分*******/
        if (l < r)
        {

            int i = l + 1;
            int j = r;
            int p = a[l];
            while (1)
            {
                while (a[i] < p)
                {
                    i++;
                }
                while (a[j] > p)
                {
                    j--;
                }
                if (i < j)
                    swap(a[i], a[j]);
                else
                    break;
            }
            swap(a[l], a[j]);
            /*********一次quick_sort***********/
            stack[++top] = l;
            stack[++top] = j - 1;
            stack[++top] = j + 1;
            stack[++top] = r;
            /* 队列实现
            inqueue(q,l);
            inqueue(q,j-1);
            inqueue(q,j+1);
            inqueue(q,r);
            */
        }
    }
}

void main()
{
    int a[] = {4, 3, 8, 2, 7, 11, 6, 1, 0, 15};
    stack_q_sort(a, 10);
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
}